home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94c.txt / 000008_icon-group-sender _Fri Dec 9 00:58:42 1994.msg < prev    next >
Internet Message Format  |  1995-02-09  |  2KB
  1. Received: by cheltenham.cs.arizona.edu; Thu, 8 Dec 1994 20:00:00 MST
  2. To: icon-group-l@cs.arizona.edu
  3. Date: Fri, 9 Dec 1994 00:58:42 GMT
  4. From: jfriedl@nff.ncl.omron.co.jp (Jeffrey Friedl)
  5. Message-Id: <JFRIEDL.94Dec9095842@shibuya.nff.ncl.omron.co.jp>
  6. Organization: Omron Corporation, Kyoto Japan
  7. Sender: icon-group-request@cs.arizona.edu
  8. References: <1994Dec7.221649.10939@cs.sfu.ca>
  9. Reply-To: jfriedl@nff.ncl.omron.co.jp
  10. Subject: Re: [Q] Algorithm for Regexp Subsumption
  11. Errors-To: icon-group-errors@cs.arizona.edu
  12.  
  13. vorbeck@cs.sfu.ca (Martin Vorbeck) writes:
  14. |> are there any algorithms out there for checking whether a regular
  15. |> expression subsumes another one, ie L(E1) is a subset of L(E2)? I have a
  16. |> "brute-force" solution along these lines:
  17. |> 
  18. |> 1. Compute equivalent finite automatas A1 (resp A2) for E1 (resp E2).
  19.  
  20. Make sure you keep the context of your problem (whetever that might be)
  21. in mind when doing this. For example, the two regexes
  22.     (a|a long regex)
  23.     a( long regex)?
  24.  
  25. (translate to your favorite flavor) are exactly equivalent in a true DFA
  26. engines (i.e. emacs), but not equivalent in some others (perl, python,
  27. etc.). FWIW, POSIX says they're the same. And FWIW, it's my opinion that
  28. being different is much more powerful.
  29.  
  30. |> Please Email any replies to
  31. |>        vorbeck@cs.sfu.ca
  32. |> as I don't usually read these newsgroups.
  33.  
  34. Now might be a good time to start.
  35.  
  36.     *jeffrey*
  37. -------------------------------------------------------------------------
  38. Jeffrey E.F. Friedl <jfriedl@omron.co.jp>  Omron Corporation, Kyoto Japan
  39. See my Jap/Eng dictionary at http://www.omron.co.jp/cgi-bin/j-e
  40.                           or http://www.cs.cmu.edu:8001/cgi-bin/j-e
  41.  
  42.